// StacksAndQueues.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

template <typename T>
class SetOfStacks
{
public:
    explicit SetOfStacks(size_t maxItemsPerStack) : _limit(maxItemsPerStack)
    {
    }

    void push(T const& value)
    {
        if (_stacks.empty())
        {
            _stacks.push_back(stack<T>());
        }
        else if (_stacks.back().size() == _limit)
        {
            _stacks.push_back(stack<T>());
        }

        _stacks.back().push(value);
    }

    T pop()
    {
        return popAt(_stacks.size() -1);

        //if (_stacks.empty())
        //{
        //    throw runtime_error("SetOfStacks is empty.");
        //}

        //auto ret = _stacks.back().top();
        //_stacks.back.pop();
        //if (_stacks.back.empty())
        //{
        //    _statics.pop_back();
        //}
        //return ret;
    }

    T popAt(int stackIndex)
    {
        if (_stacks.empty())
        {
            throw runtime_error("SetOfStacks is empty.");
        }

        if (stackIndex >= _stacks.size())
        {
            throw runtime_error("stackIndex is out of range.");
        }

        auto ret = _stacks[stackIndex].top();
        _stacks[stackIndex].pop();

        if (_stacks[stackIndex].empty())
        {
            _stacks.erase(_stacks.begin() + stackIndex);
        }
        return ret;
    }

private:
    vector<stack<T>> _stacks;
    size_t _limit;
};

void tetSetOfStacks()
{
    SetOfStacks<int> x(2);
    for (int i = 0; i < 10; i++)
    {
        x.push(i);
    }

    for (int i = 0; i < 11; i++)
    {
        try 
        {
            cout << x.popAt(0) << ", ";
        }
        catch (runtime_error const& error)
        {
            cout << error.what() << " "; 
        }
    }
    cout << endl;
}

template<typename T>
class Queue
{
public:
    void add(T const& value)
    {
        _new.push(value);
    }

    T remove()
    {
        if (_old.empty())
        {
            shift();
        }

        if (_old.empty())
        {
            throw runtime_error("Queue is empty.");
        }

        T x = _old.top();
        _old.pop();
        return x;
    }

private:
    void shift()
    {
        while (!_new.empty())
        {
            _old.push(_new.top());
            _new.pop();
        }
    }

    stack<T> _new;
    stack<T> _old;
};

void testQueue()
{
    // Question 3.5
    Queue<int> queue;
    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.add(4);
    queue.add(5);

    try
    {
        while (true)
        {
            cout << queue.remove() << endl;
        }
    }
    catch (runtime_error const& e)
    {
        cout << e.what() << endl;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    tetSetOfStacks();
    testQueue();
    cin.get();
	return 0;
}

